#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/4 17:01
# @USER    : Shengji He
# @File    : LetterCombinationsPhoneNumber.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


class Solution:
    def letterCombinations(self, digits: str) -> [str]:
        """
        Given a string containing digits from 2-9 inclusive,
        return all possible letter combinations that the number could represent.

        A mapping of digit to letters (just like on the telephone buttons) is given below.
        Note that 1 does not map to any letters.

        Example:
            Input: "23"

            Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

        :param digits: str
        :return: List[str]


        Note:
        Although the above answer is in lexicographical order, your answer could be in any order you want.
        """
        letter_dict = {'2': 'abc',
                       '3': 'def',
                       '4': 'ghi',
                       '5': 'jkl',
                       '6': 'mno',
                       '7': 'pqrs',
                       '8': 'tuv',
                       '9': 'wxyz'}
        if len(digits) == 0:
            return []
        ans = list(letter_dict[digits[0]])
        idx = 1
        while idx < len(digits):
            ans = [a + s for s in list(letter_dict[digits[idx]]) for a in ans]
            idx += 1
        return ans


if __name__ == '__main__':
    S = Solution()
    digits = ''
    print(S.letterCombinations(digits))
    print('done')
